/**
 * LeetCode21：合并两个有序链表
 * 将两个升序链表合并成一个新的升序链表并返回
 */

function ListNode(val){
    this.val = val;
    this.next = null;
}

/**
 *
 * @param {ListNode} t1
 * @param {ListNode} t2
 * @return {ListNode}
 */
var mergeTwoLists = function (t1,t2){
    const res = new ListNode(0);
    let p = res;
    let p1 = t1;
    let p2 = t2;
    while (p1 && p2){
        if (p1.val < p2.val){
            p.next = p1;
            p1 = p1.next;
        }else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1){
        p.next = p1;
    }
    if (p2){
        p.next = p2;
    }
    return res.next;
}

//时间复杂度：O(n)
//空间复杂度：O(1)